package Array.easy;

/**
 * 1. 问题描述
 *      求出数组种所有奇数长度的子数组的和
 * 2. 算法分析
 *      1. 穷举法
 *
 *      2. 计数法
 *          我们需要从另外一个角度去看这个问题：我们想要求所用奇数长度的子数组的和
 *          这等价于如果我们直到每个数字在多少个奇数长度的数组种出现，我们就可以求
 *          出该问题，假设count[i]代表第i个元素nums[i]出现的次数，则奇数数组的
 *          和为：
 *              count[0]*nums[0]+...+count[len-1]*nums[len-1]
 *          整个问题划归为我们如何确定每个元素出现的次数?
 *          假设我们现在需要求出第i个元素的出现次数，通过第i个元素我们可以将数组划分为三个部分
 *              A{0,1,2,...,i-1} A{i} A{i+1,i+2,...,N-1} 数组的长度为N
 *          考虑什么样的数组长度为奇数而且还包含A{i}?
 *          只有两种情况：
 *              1. 左边为奇数长度，右边为奇数长度
 *              2. 左边为偶数长度，右边为偶数长度
 *           所以我们只需要求出左/右边奇数长度的子数组数，左右的偶数长度的子数组数即可求出当前元素
 *           出现在奇数数组种的次数
 *           下面给出具体的计算过程
 *              1. leftOdd
 *                  {i-1},{i-1,i-2,i-3},...
 *                  i - (2k-1) >= 0 k = 1, 2, 3, ...
 *                  k <= (i+1)/2
 *              2. leftEven
 *                  {i-1,i-2},{i-1,i-2,i-3,i-4},...
 *                  i - (2k - 2) >= 0
 *                  k <= i/2 + 1
 *              3. rightOdd
 *                  {i+1},{i+1,i+2,i+3},....
 *                  i + (2k-1) <= N - 1
 *                  k <= (N - i)/2
 *
 *              4. rightEven
 *                  {i+1,i+2},{i+1,i+2,i+3,i+4},...,
 *                  i + (2k-2) <= N - 1
 *                  k <= (N-i+1)/2
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 所有奇数长度的子数组和 {
    public static void main(String[] args) {
        int[] arr = {1,4,2,5,3};
        System.out.println(sumOddLengthSubarrays(arr));
    }

    public static int sumOddLengthSubarrays(int[] arr) {
        int sum = 0;
        int len = arr.length;
        for (int i = 0; i < arr.length; i++) {
            int leftOdd = (i+1)/2; // 记录arr[i]左边的奇数数组的个数(这些数组以arr[i]结尾)
            int leftEven = i/2+1; // 左边偶数数组个数
            int rightOdd = (len - i)/2; // 右边奇数
            int rightEven = (len-i+1)/2; // 右边偶数
            sum += arr[i] * (leftOdd*rightOdd+leftEven*rightEven);
        }
        return sum;
    }
}
